package simple;

import data.TreeNode;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/12/27 11:50
 */
public class No404_左叶子之和 {
    public static void main(String[] args) {
        Solution404 solution404 = new Solution404();
        TreeNode data = new TreeNode(3);
        data.left = new TreeNode(9);
        data.right = new TreeNode(20);
        data.right.left = new TreeNode(15);
        data.right.right = new TreeNode(7);
        int sum = solution404.sumOfLeftLeaves(data);
        System.out.println(sum);
    }
}

class Solution404 {
    public int sumOfLeftLeaves(TreeNode root) {
        //数组??? 想新颖一下,嘎嘎嘎嘎
        //深度优先搜索,递归
        //数组作用:将值放在数组,进行值带入
        int[] sum = new int[]{0};
        getZhi(root, sum);
        return sum[0];
    }

    public void getZhi(TreeNode root, int[] sum) {
        if (root == null || isLeafNode(root)) {
            return;
        }
        //有节点
        //左节点不为空
        TreeNode leftTree = root.left;
        TreeNode rightTree = root.right;
        if (leftTree != null) {
            if (isLeafNode(leftTree)) {
                //值相加
                sum[0] += leftTree.val;
            }
            //值带入
            getZhi(root.left, sum);
        }

        if (rightTree != null) {
            //操作右节点
            getZhi(root.right, sum);
        }
    }

    //判断是不是叶子
    public boolean isLeafNode(TreeNode node) {
        return node.left == null && node.right == null;
    }
}



    //public int sumOfLeftLeaves(TreeNode root) {
    //    if (root == null) {
    //        return 0;
    //    }
    //    //左叶子:本身无子节点,父节点的左边节点
    //    //队列
    //    Queue<TreeNode> queue = new ArrayDeque<>();
    //    queue.offer(root);//[3]
    //    int res = 0;
    //    while (!queue.isEmpty()) {
    //        TreeNode check = queue.remove();//3
    //        TreeNode leftTree = check.left;
    //        TreeNode rightTree = check.right;
    //        //操作左右子节点
    //        if (isLeafNode(check)) {
    //            continue;
    //        } else {
    //            //说明一定有子节点
    //            if (leftTree != null) {
    //                //判断是叶子节点
    //                if (isLeafNode(leftTree)) {
    //                    //加和
    //                    res += leftTree.val;
    //                }
    //                //队列加元素
    //                queue.offer(leftTree);
    //            }
    //
    //            if (rightTree != null) {
    //                queue.offer(rightTree);
    //            }
    //        }
    //    }
    //    return res;
    //}
    //
    ////判断是不是叶子
    //public boolean isLeafNode(TreeNode node) {
    //    return node.left == null && node.right == null;
    //}